package datastructure.find;

/**
 * @author MaoLin Wang
 * @description TODO
 * @date 2020/8/26 1:17 下午
 */
public class BinarySearchST<Key extends Comparable<? super Key>, Value> {
    private Key[] keys;
    private Value[] values;
    private int size;

    public BinarySearchST(int size) {
        keys = (Key[]) new Comparable[size];
        values = (Value[]) new Comparable[size];
    }

    public Value get(Key key) {
        if (key == null) {
            return null;
        }
        int i = rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            return values[i];
        }
        return null;
    }

    public void put(Key key,Value value){
        if (key==null){
            return;
        }
        if (value==null){
            delete(key);
            return;
        }
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
           values[i]=value;
        }else {
            if (size==keys.length){
                enlarge(keys.length*2);
            }
            for (int j = size; j >i ; j--) {
                keys[j]=keys[j-1];
                values[j]=values[j-1];
            }
            keys[i]=key;
            values[i]=value;
            size++;
        }
    }

    private void enlarge(int size) {
        Key[]old=keys;
        int oldLen=keys.length;
        Value[]oldValue=values;
        keys= (Key[]) new Comparable[size];
        values= (Value[]) new Comparable[size];
        for (int i = 0; i < oldLen; i++) {
            keys[i]=old[i];
            values[i]=oldValue[i];
        }
    }

    public void delete(Key key) {
        if (key==null){
            return;
        }
        int i=rank(key);
        if (i<size && keys[i].compareTo(key)==0){
            for (int j = i; j <size-1 ; j++) {
                keys[j]=keys[j+1];
                values[j]=values[j+1];
            }
            size--;
        }
    }

    private int rank(Key key) {
        if (key == null) {
            return -1;
        }
        int left = 0;
        int right = size - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (key.compareTo(keys[mid])<0){
                right=mid-1;
            }else if (key.compareTo(keys[mid])>0){
                left=mid+1;
            }else {
                return mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        BinarySearchST<String, String> st = new BinarySearchST<>(6);
        st.put("1","wml1");
        st.put("3","wml7");
        st.put("2","wml2");
        st.put("8","wml8");
        st.put("5","wml5");
        st.put("6","wml6");
        System.out.println(st.get("1"));
        System.out.println(st.get("3"));
        System.out.println(st.get("2"));
        System.out.println(st.get("8"));
        System.out.println(st.get("5"));
        System.out.println(st.get("6"));
        st.delete("3");
        System.out.println(st.get("3"));
        st.put("5","haha");
        System.out.println(st.get("5"));
    }
}
